1. Field of the Invention
This invention relates to memory management of data structures in a striped pipelined set of memories.
2. Related Art
In a pipelined data structure such as described in the incorporated disclosures, a sequence of memories are used for pipelined lookup and update operations on a compact data structure in a pipelined architecture. As described in the incorporated disclosures, the data structure is maintained in a sequence of memories. It is desirable to manage use of those memories so that update operations can be performed for those data structures while simultaneously maintaining (a) low worst-case memory requirement, that is, relatively good worst-case memory utilization, (b) low update complexity, that is low complexity of hardware and software for update operations, and (c) low worst-case time requirement, that is, relatively good worst-case speed.
Accordingly it would be desirable to have a technique for update operations performed on a compact data structure in a pipelined architecture, in which the data structure includes stripe for a set of nodes in a hybrid trie, and that simultaneously maintains the desirable features noted above. It would be advantageous if that technique were well adapted to pipelined operation, such as further described in the incorporated disclosures. The following features would be advantageous:
It would be advantageous if that technique were capable of relatively rapid insertion of new data elements while minimizing time requirements.
It would be advantageous if that technique were capable of relatively rapid removal of old data elements while minimizing time requirements.
These advantages and others are provided in an embodiment of the invention, described herein, including a memory management technique in which individual nodes in a hybrid trie are striped across a set of pipelined memories.
The invention provides a method and system for memory management, in which at least some individual nodes in a hybrid trie are striped across a set of pipelined memories. Memory management is performed for a hybrid trie including both branch-search nodes and leaf-search nodes and maintained in a sequence of pipelined memories. The method of memory management provides for insertion and removal of data elements within the hybrid trie and for storing at least some of the nodes (the leaf-search nodes) in stripes across a sequence of the memories. Memory management is performed for the leaf-search nodes (those nodes that are stored in stripes across a sequence of the memories), by selecting stripes from the possible subsequences of those memories, that are suited to pipelined operations performed on the memories. In a preferred embodiment, an invariant condition is maintained for families of those stripes, in which exactly one cell block in each family is labeled xe2x80x9csparsexe2x80x9d and that cell block is used in techniques for allocation and de-allocation of entries.
The invention has general applicability to memory management in which data structures are distributed across a set of distinct memories. None of the e applications are limited specifically to update operations for hybrid tries, or to data strictures for lookup of message header information, nor are they necessarily related to the specific applications disclosed herein.